// 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

// 异位词 指字母相同，但排列不同的字符串。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


// 33超时

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;


// 看了题解，滑动窗口
// 执行用时：
// 8 ms
// , 在所有 C++ 提交中击败了
// 96.75%
// 的用户
// 内存消耗：
// 8.5 MB
// , 在所有 C++ 提交中击败了
// 45.43%
// 的用户

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if(s.size()<p.size()){
            return res;
        }
        int s_cnt[26] = {0};
        int p_cnt[26] = {0};
        for(int i=0;i<p.size();i++){
            p_cnt[p[i]-'a']++;
            s_cnt[s[i]-'a']++;
        }
        if(check(s_cnt,p_cnt)){
            res.push_back(0);
        }
        int begin=0,end=p.size()-1;
        while(end<s.size()-1){
            s_cnt[s[begin++]-'a']--;
            s_cnt[s[++end]-'a']++;
            if(check(s_cnt,p_cnt)){
                res.push_back(begin);
            }
        }
        return res;
    }
    bool check(int s[],int p[]){
        for(int i=0;i<26;i++){
            if(s[i]!=p[i]){
                return false;
            }
        }
        return true;
    }
};